Batch 3 - Class 224 - Random Walks and Color Triangles

• (Cornell) Two people have two consecutive natural numbers pasted on their heads, which they can't see but the other person can see. First person starts by asking the other if she knows what her number is. If she says yes, game ends. If she says no, she asks the first person if he knows his number. And so on. Does the game ever end? Sometimes? Never? Always?
• Let kids think -intuitively, the answer is that the game doesn't end
• Ask someone what is your name repeatedly to reinforce this false intuition - it seems that asking the same question again and again doesn't help
• What if the second person sees a number 1 on first person's forehead? Oh, so it does finish in some cases? Which ones?
• What if first person sees a number "2" on second person's forehead? What can he reason by hearing a "no" from the second person? What if there is a "4" on one person's head?
• Can we form an induction hypothesis?
• The game ends in at most 2n steps, if n is the lower of the two numbers
• Note that in some cases, forming the hypothesis can be challenging
• Base case is already proven
• Prove the induction step

• Ask students the probability before rolling the dice. Allow them to place 6 counters in the five circles to demonstrate their "bets"
• Now give each student chances in turn, and get them to play - observe the probability. Whenever a particular play lands up in a circle, students get to remove their counter (if any) on that circle. The student to remove all their counter first wins.
• Discuss why that happens - run a though experiment of starting with a million plays, and how they would split at each stage.

• What are the actual probabilities? Lets do the thought experiment with a million plays.
• What if there was a 90% chance of going left, and 10% chance of going right?

• Can you predict what will be the final color if you start from 

  
• What if we started from a longer sequence, like 

  
• Can you try and predict for three-long sequences. Is there a pattern or shortcut? Figure it out for all three dots.
• Now try to create all patterns for four dots. Can you predict the final dot? Figure out for all possibilities.
• Can you find any simplifying patterns in four dots?
• How about larger strings of dots? Five, Six, Seven? Can your simplifying patterns help?
• Try the above sequence now
• What about a longer sequence of 28 dots? 

  
• Can you think what is happening mathematically at each step?
• There are three colors, so think about modulo-3 math. How are two colors adding up?
• If you have a and b, then the result is -a-b modulo 3. 
• What will happen at next step? -(-a-b)-(-b-c)=a+2b+c. This looks like the sequence we saw in our random walks exercise!
• So, if you start from n-sequence, there will be n steps, and sign will change at each step. So (-1)^n * Sum with each position from 0 to (n-1), C(n-1,k)a(k), where a(k) is the kth item. This number modulo 3 is the final color.

• (Dudeney 365) There are two jars of 10 liters full of water, and two empty ones of 5 and 4 liter capacity. You want to have 3 liters each in the smaller jars, without wasting any water. Devise the sequence of steps.
• Answer: